package array

// 方法1
func longestPalindrome(s string) string {

	var left, right int
	max := 0
	byteList := []byte(s)

	for i := 0; i < len(byteList)-1; i++ {
		l1, r1 := helper05(byteList, i, i)
		l2, r2 := helper05(byteList, i, i+1)
		if r1-l1+1 > max {
			left, right = l1, r1
			max = r1 - l1 + 1
		}
		if r2-l2+1 > max {
			left, right = l2, r2
			max = r2 - l2 + 1
		}
	}

	return string(byteList[left : right+1])

}

func helper05(s []byte, left int, right int) (int, int) {

	for ; left >= 0 && right < len(s) && s[left] == s[right]; left, right = left-1, right+1 {

	}
	return left + 1, right - 1
}

// 动态规划
func longestPalindrome2(s string) string {

	var i, j int
	max := 1
	byteList := []byte(s)
	dp := make([][]bool, len(s))
	for i := range dp {
		dp[i] = make([]bool, len(s))
		for j := range dp[i] {
			dp[i][j] = true
		}
	}

	for right := 0; right < len(s); right++ {
		for left := 0; left < right; left++ {
			if byteList[left] == byteList[right] {
				dp[left][right] = dp[left+1][right-1]
				if dp[left][right] && right-left+1 > max {
					max = right - left + 1
					i = left
					j = right
				}
			} else {
				dp[left][right] = false
			}
		}
	}

	return string(byteList[i : j+1])

}
